package com.exercises;

import com.alibaba.fastjson.JSONObject;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Exercise752 {
    public static void main(String[] args) {
        System.out.println(openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
//        System.out.println(JSONObject.toJSON(nextValue("1000")));
    }


    public static int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) return 0;
        Set<String> dead = Stream.of(deadends).collect(Collectors.toSet());
        if (dead.contains("0000")) return -1;
        int step = 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        Set<String> seen = new HashSet<>();
        seen.add("0000");

        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; ++i) {
                String status = queue.poll();
                Set<String> nextValues = nextValue(status);
                if (nextValues.contains(target)) return step;
                nextValues.stream().filter(nextStatus -> !seen.contains(nextStatus) && !dead.contains(nextStatus))
                        .forEach(nextStatus -> {
                            queue.offer(nextStatus);
                            seen.add(nextStatus);
                        });
            }
        }


        return -1;
    }


    public static Set<String> nextValue(String value) {
        Set<String> set = new HashSet<>();
        char[] chars = value.toCharArray();
        for (int i = 0; i < 4; i++) {
            char c = chars[i];
            chars[i] = c == '9' ? '0' : (char) (c + 1);
            set.add(new String(chars));
            chars[i] = c == '0' ? '9' : (char) (c - 1);
            set.add(new String(chars));
            chars[i] = c;
        }
        return set;
    }
}
